/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.Collections;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.Scanner;

public class LexiconArrayList implements LexiconInterface {
  /**
   * Load the words from an input source and store them in this lexicon.
   * 
   * @param input
   *          A scanner that will provide the entire dictionary.
   */
  private ArrayList<String> words = new ArrayList<String>();
  private int size;
  public void load(Scanner input) {
    while (input.hasNext()) {
      String nextStr = input.next();
      words.add(nextStr);
    }
    Collections.sort(words);
    size = words.size()-1;
  }
  
  

  /**
   * If the prefix is in the lexicon, returns true.
   * 
   * @param s
   *          The word to search for.
   * @return True if the lexicon contains s.
   */
  public boolean containsPrefix(String s) {
	int low = 0;
	int high = size;
    return containsPrefixHelper(s,low,high);
  }

  /**
   * Recursive helper for containsPrefix.
   * Compares the string s to words[mid] and adjusts low and high until a final result is achieved
   * @param s		String to find
   * @param low		Low boundary
   * @param high	High boundary
   * @return		True or false depending on if the prefix is found
   */
  private boolean containsPrefixHelper(String s, int low, int high){
	 if(high < low){
		 return false;
	 }
	 int mid = low+(high-low)/2;
	 int result = s.compareTo(words.get(mid));
	 if(words.get(mid).startsWith(s) || result == 0){
		 return true;
	 }else if(result>0){
		 return containsPrefixHelper(s,mid+1,high);
	 }else if(result<0){
		 return containsPrefixHelper(s,low,mid-1);
	 }else{
		 return false;
	 }
  }
  /**
   * If the word is in the lexicon, returns true.
   * 
   * @param s
   *          The word to search for.
   * @return True if the lexicon contains s.
   */
  public boolean contains(String s){
    return Collections.binarySearch(words, s)>=0;
  }

@Override
public Iterator<String> iterator() {	
	return words.iterator();
}
}
